package history

import "github.com/pkg/errors"

type Node struct {
	Val  int
	Next *Node
}

/**
 * @description: 链表排序
 * @keyword:
 * @author: kami
 * @date 2024/3/19 17:18
 */
func sortList(head *Node) *Node {
	if head == nil || head.Next == nil {
		return head
	}
	var slow = head
	var fast = head.Next
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	var rightHead = slow.Next
	slow.Next = nil
	var left = sortList(head)
	var right = sortList(rightHead)
	var virtualHead = &Node{}
	var pre = virtualHead
	for left != nil && right != nil {
		if left.Val < right.Val {
			pre.Next = left
			left = left.Next
		} else {
			pre.Next = right
			right = right.Next
		}
		pre = pre.Next
	}
	if left != nil {
		pre.Next = left
	} else if right != nil {
		pre.Next = right
	}
	return virtualHead.Next
}

func searchRange(nums []int, target int) []int {
	var size = len(nums)
	if size == 0 || nums[0] > target || nums[size-1] < target {
		return []int{-1, -1}
	}
	if nums[0] == target && nums[size-1] == target {
		return []int{0, size - 1}
	}
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = left + (right-left)/2
		if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			// 左端点
			var curRight = mid
			for left <= curRight {
				mid = left + (curRight-left)/2
				if nums[mid] < target {
					left = mid + 1
				} else {
					if mid == 0 || nums[mid-1] < target {
						left = mid
						break
					}
					curRight = mid - 1
				}
			}
			// 右端点
			var curLeft = mid
			for curLeft <= right {
				mid = curLeft + (right-curLeft)/2
				if nums[mid] > target {
					right = mid - 1
				} else {
					if mid == len(nums)-1 || nums[mid+1] > target {
						right = mid
						break
					}
					curLeft = mid + 1
				}
			}
			return []int{left, right}
		}
	}
	return []int{-1, -1}
}

/**
 * @description: 找到数组第2大的数字
 * @keyword:
 * @author: kami
 * @date 2024/3/21 15:53
 */
func findNum(nums []int) (int, error) {
	if len(nums) <= 1 {
		return 0, errors.Errorf("num size is less than 1")
	}
	var firstMax = nums[0]
	var secondMax = nums[0]
	//
	for i := 0; i < len(nums); i++ {
		if nums[i] > firstMax {
			secondMax = firstMax
			firstMax = nums[i]
		} else if nums[i] < firstMax && nums[i] > secondMax {
			secondMax = nums[i]
		}
	}
	if firstMax == secondMax {
		return 0, errors.Errorf("no second num")
	}
	return secondMax, nil
}
